#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#define MOD 1000000007

class Solution
{
public:
    std::vector<int> hitBricks(std::vector<std::vector<int>>& grid, std::vector<std::vector<int>>& hits)
    {
        int glen = grid.size();
        int m = grid[0].size();
        int hlen = hits.size();
        std::vector<int> res(hlen, 0);
        if (glen == 1)
        {
           
            return res;
        }
        int row, col;
        for (int i = 0; i < hlen; i++)
        {
            row = hits[i][0];
            col = hits[i][1];
            grid[row][col] -= 1;
        }
        for (int j=0;j<m;j++)
        {
            dfs(grid,0,j,glen,m);
        }
        for (int i=hlen-1;i>=0;i--)
        {
            row = hits[i][0];
            col = hits[i][1];
            grid[row][col] += 1;
            if (worth(row,col,grid,glen,m))
            {
                res[i]=dfs(grid,row,col,glen,m)-1;
            }
        }
        return res;
    }
    bool worth(int i, int j,std::vector<std::vector<int>>& grid,int n,int m) {
        return grid[i][j] == 1
            &&
            (i == 0
            || (i > 0 && grid[i - 1][j] == 2)
            || (i < n - 1 && grid[i + 1][j] == 2)
            || (j > 0 && grid[i][j - 1] == 2)
            || (j < m - 1 && grid[i][j + 1] == 2));
    }

    int dfs(std::vector<std::vector<int>>& board, const int& i, const int& j, const int& n, const int& m)
    {
        if (i < 0 || i >= n || j < 0 || j >= m || board[i][j] != 1)
        {
            return 0;
        }
        board[i][j] = 2;
        return 1 + dfs(board, i + 1, j, n, m) + dfs(board, i - 1, j, n, m)
        + dfs(board, i, j + 1, n, m) +dfs(board, i, j - 1, n, m);
    }
};
